package algorithm.leetcode.I101to200;

/**
 * 本身不难,难的是要求对数时间复杂度
 * key: 二分查找的变体,关键是要想通二分查找在这里是work的
 *
 * 因为题目只要求出来**任意一个**,并且数组不存在挨着的元素相等的情况,我们可以这样理解查找过程：
 *
 * 1. 如果当前比右边小,那么肯定在右边会有峰顶,最差情况走到头,也是一个峰顶, e.g. (5),10；
 * 2. 如果当前比左边小,那么肯定在左边会有峰顶,最差情况走到头,也是一个峰顶, e.g. (10),5.
 * 实际上,我们查找过程,只需要比较一个元素和 它的右边元素就可以.
 * 所以,比较一个元素 和 它右边的元素,
 *
 * 如果是上坡,那么 mid 不可能是答案,让 i+1 ；
 * 如果是下坡,那 mid 可能是答案,让 j = mid.
 * 这正好就只需要比较挨着的两个元素.
 *
 */

public class Q162 {

    public int findPeakElement(int[] nums) {
        return findHelper(nums, 0, nums.length-1);
    }

    public int findHelper(int[] nums, int left, int right) {
        if (left == right) return left;
        else {
            int mid = (right-left)/2+left;
            if (nums[mid] < nums[mid+1]) return findHelper(nums, mid+1, right);
            else return findHelper(nums, left, mid);
        }
    }

    public static void main(String[] args) {
        Q162 q162 = new Q162();
        System.out.println(q162.findPeakElement(new int[]{1, 2, 3, 1}));
    }
}
